243A - The Brand New Function - CodeForces Solution

#include <bits/stdc++.h>
#define ff first
#define ss second

using namespace std;
using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using vi = vector<int>;

using tii = tuple<int,int,int>;
// auto [a,b,c] = ...
// .insert({a,b,c})

// https://codeforces.com/blog/entry/91347
#define dbg(...) logger(#__VA_ARGS__, __VA_ARGS__)
template<typename ...Args>
void logger(string vars, Args&&... values) {
    cout << vars << " = ";
    string delim = "";
    (..., (cout << delim << values, delim = ", "));
    cout << "\n";
}

const int oo = (int)1e9 + 5; //INF to INT
const ll OO = 0x3f3f3f3f3f3f3f3fLL; //INF to LL

const int MAXN = 1e5 + 100;
const int MAXB = 20;

int nxt[MAXN][MAXB];

void solve() {  

    int N;
    cin >> N;

    vector<int> arr(N);

    for(auto &x : arr) {
        cin >> x;
    }

    //for every bit, the next position with i-bit on

    for(int b = 0; b < MAXB; b++) {
        int pos = -1;
        for(int i = N - 1; i >= 0; i--) {
            if(arr[i] & (1LL << b)) pos = i;
            nxt[i][b] = pos;
        }
    }

    vector<int> ans;

    for(int i = 0; i < N; i++) {
        vector<int> pos = { i };
        for(int b = 0; b < MAXB; b++) if( !(arr[i] & (1 << b)) ) {
            if(nxt[i][b] != -1)
                pos.push_back(nxt[i][b]);
        }
        int curval = arr[i];
        sort(pos.begin(), pos.end());
        for(auto &p : pos) {
            curval |= arr[p];
            ans.push_back(curval);
            //dbg(i, p, curval);
        }
    }
    
    sort(ans.begin(), ans.end());
    ans.erase(unique(ans.begin(), ans.end()), ans.end());

    cout << (int)ans.size() << "\n";

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int t = 1;
    //cin >> t;
    
    while(t--) {
        solve();
    }

}